#include <bits/stdc++.h>
using namespace std;

// 最长递增子序列和最长不下降子序列
// 给定一个整数数组nums
// 找到其中最长严格递增子序列长度、最长不下降子序列长度
// 力扣测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/
// 洛谷测试链接 ：https://www.luogu.com.cn/problem/B3637

class Solution 
{
public:
    // 普通解法的动态规划
	// 时间复杂度O(n^2)，数组稍大就会超时
    int lengthOfLIS1(vector<int>& nums) 
    {
        int n = nums.size();
        int ret = 0;
        int dp[n]; // 以某个位置为结尾的最长递增子序列的长度
        for(int i = 0; i < n; ++i)
        {
            dp[i] = 1;
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }

    int lengthOfLIS2(vector<int>& nums) 
    {
        int n = nums.size();
        int ends[n];
        int len = 0;
        for(int i = 0, find; i < n; ++i)
        {
            find = bs1(ends, len, nums[i]);
            if(find == -1) ends[len++] = nums[i];
            else ends[find] = nums[i];
        }
        return len;
    }

    // "最长递增子序列"使用如下二分搜索 :
	// ends[0...len-1]是严格升序的
    // ends[i] : 目前所有长度为i+1的递增子序列的最小结尾
	// 在其中找到>=num的最左位置，如果不存在返回-1
    int bs1(int* ends, int len, int num)
    {
        int l = 0, r = len - 1, m, ans = -1;
        while(l <= r)
        {
            int m = (l + r) / 2;
            if(num <= ends[m]) 
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans;
    }

	// "最长不下降子序列"使用如下二分搜索 :
	// ends[0...len-1]是不降序的
	// 在其中找到>num的最左位置，如果不存在返回-1
	// 求"最长不下降子序列"就是在lengthOfLIS中把bs1方法换成bs2方法
	// 整体测试已经用对数器测了
    int bs2(int* ends, int len, int num)
    {
        int l = 0, r = len - 1, m, ans = -1;
        while(l <= r)
        {
            m = (l + r) / 2;
            if(num < ends[m])
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans;
    }
};



// 使用标准库的的二分查找
class Solution 
{
public:
    // 最长递增子序列
    int lengthOfLIS(vector<int>& nums) 
    {
        vector<int> g;
        for(int x : nums)
        {
            // lower_bound 返回第一个大于或等于 x 的元素的位置
            auto it = lower_bound(g.begin(), g.end(), x);
            if(it == g.end()) g.push_back(x);
            else *it = x;
        }
        return g.size();
    }

    // 最长不下降子序列
    int lengthOfNoDecreasing(vector<int>& nums) 
    {
        vector<int> g;
        for(int x : nums)
        {
            // lower_bound 返回第一个大于 x 的元素的位置
            auto it = upper_bound(g.begin(), g.end(), x);
            if(it == g.end()) g.push_back(x);
            else *it = x;
        }
        return g.size();
    }
};


// 线段树的解，暂时不要求掌握，可以等左神进行讲解
// 如果向提前了解，可以看下面的资料
// https://oi-wiki.org/ds/seg/
// 以下是三个讲解线段树的视频，可以看一下
// https://www.bilibili.com/video/BV18t4y1p736/?spm_id_from=333.999.0.0
// https://www.bilibili.com/video/BV1it4y1L7kL/?spm_id_from=333.999.0.0
// https://www.bilibili.com/video/BV15D4y1G7ms/?spm_id_from=333.999.0.0

class Solution 
{
    vector<int> mx; // 记录区间的最大值

    // 单点更新：将idx位置的值更新成val
    void modify(int o, int l, int r, int idx, int val)
    {
        // 节点o所管辖的区间是[l, r]
        if(l == r)
        {
            mx[o] = val;
            return;
        }
        int m = (l + r) / 2;
        if(idx <= m) modify(2 * o, l, m, idx, val); // idx位置在左子树
        else modify(2 * o + 1, m + 1, r, idx, val); // idx位置在右子树
        mx[o] = max(mx[2 * o], mx[2 * o + 1]); // 维护父节点的最大值
    }

    // 区间查询：查询[L, R]范围内的最大值
    // L和R在整个递归过程中就是一个常量
    int query(int o, int l, int r, int L, int R)
    {
        if(L <= l && r <= R) return mx[o];
        int ret = 0, m = (l + r) / 2;
        if(L <= m) ret = query(2 * o, l, m, L, R);
        if(R > m) ret = max(ret, query(2 * o + 1, m + 1, r, L, R));
        return ret;
    }

public:
    int lengthOfLIS(vector<int>& nums) 
    {
        // 加上10010避免负数，因为线段树节点编号是从1开始的
        // 同时线段树根节点的编号为1
        int n = *max_element(nums.begin(), nums.end()) + 10010;
        mx.resize(4 * n); // 开最大值的四倍空间就足够用了
        for(int x : nums)
        {
            x += 10010;
            int ret = 1 + query(1, 1, n, 1, x - 1); // 区间查询
            modify(1, 1, n, x, ret); // 单点更新
        }
        return mx[1];
    }
};